// 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

#include<bits/stdc++.h>
using namespace std;

// 迭代O(n)

// 执行用时：
// 4 ms
// , 在所有 C++ 提交中击败了
// 91.12%
// 的用户
// 内存消耗：
// 8 MB
// , 在所有 C++ 提交中击败了
// 81.48%
// 的用户

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 思路
        // 遍历list，定义结果链开头，每次找到一个节点就把结果链接到当前节点的next，结果链head变为当前节点
        ListNode* cur = head;
        // 结果链，初始化nullptr
        ListNode* pre=nullptr;
        while(cur){
            // 保存next
            ListNode* tree_next = cur->next;
            // 当前节点作为结果链head
            cur->next = pre;
            // 变换结果链head地址
            pre = cur;

            // 下一节点
            cur = tree_next;
        }
        return pre;
    }

};